package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * SubtreeWithAllDeepest
 * <p>
 * 865. 具有所有最深节点的最小子树
 *
 * @author: lupeng6
 * @create: 2021/2/5 14:42
 */
public class SubtreeWithAllDeepest {

    public static void main(String[] args) {
        Integer[] arr = {0, 3, 1, 4, null, 2, null, null, 6, null, 5};
        TreeNode treeNode = TreeMain.array2tree(arr);
        TreeNode node = new SubtreeWithAllDeepest().subtreeWithAllDeepest(treeNode);
        System.out.println(node);
    }

    private Map<TreeNode, TreeNode> parent = new HashMap<>();
    private Map<Integer, List<TreeNode>> depthMap = new HashMap<>();
    private int maxDepth = Integer.MIN_VALUE;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        dfsInit(root, 0);
        List<TreeNode> treeNodes = depthMap.get(maxDepth);

        if (treeNodes.size() == 1) {
            return treeNodes.get(0);
        }

        // 最深节点大于1一个
        TreeNode first = treeNodes.get(0);
        Map<TreeNode, Integer> height = new HashMap<>();
        int h = 0;
        height.put(first, h);

        while (first != null) {
            h++;
            TreeNode p = parent.get(first);
            if (p != null) {
                height.put(p, h);
            }
            first = p;
        }

        // 遍历其他最深节点, 寻找最近公共节点
        TreeNode maxHeightNode = treeNodes.get(0);

        for (int i = 1; i < treeNodes.size(); i++) {
            TreeNode node = treeNodes.get(i);
            while (node != null) {
                TreeNode p = parent.get(node);
                if (height.containsKey(p)) {
                    if (maxHeightNode != p && height.get(maxHeightNode) < height.get(p)) {
                        maxHeightNode = p;
                    }
                    break;
                }
                node = p;
            }
        }

        return maxHeightNode;
    }

    void dfsInit(TreeNode node, int depth) {
        if (node.left != null) {
            parent.put(node.left, node);
            dfsInit(node.left, depth + 1);
        }

        depthMap.putIfAbsent(depth, new ArrayList<>());
        depthMap.get(depth).add(node);
        maxDepth = Math.max(maxDepth, depth);

        if (node.right != null) {
            parent.put(node.right, node);
            dfsInit(node.right, depth + 1);
        }
    }
}
